#include<bits/stdc++.h>
// #include<iostream>
// #include <vector>
// #include <algorithm>
// #include <unordered_set>
using namespace std;
//--------------------------------------------------------------------------------------

void Print(const vector<int>& num)
{
	for (auto i : num)
	{
		cout << i << " ";
	}
}

//--------------------------------------------------------------------------------------
int Getnext(int n)
{
    int sum = 0;
    int v;

        while (n)
        {
            v = n % 10;
            // sum += pow(v,2);
            n /= 10;

        }
        return sum;
}

bool isHappy(int n)
{
    int s=n,f=Getnext(n);
    while(s!=f&&f!=1)
    {
        s=Getnext(n);
        f=Getnext(Getnext(f));

    }
    return f==1;

}
//--------------------------------------------------------------------------------------
int triangleNumber(vector<int> &nums)
{
    if (nums.size() < 3)
        return 0;
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int sm = 0;

    // 外层循环：固定最小边 f（i 更直观，这里沿用原变量名 f）
    for (int f = 0; f < n - 2; ++f)
    {
        // 关键优化1：t 初始化为 f+2（而非随 s 重置），且仅在 f 变化时重置
        // 中层循环：固定中间边 s（s 从 f+1 开始）
        int t = f + 2;
        for (int s = f + 1; s < n - 1; ++s)
        {

            // 关键优化2：t 不回溯，从当前位置继续右移，寻找最大满足条件的 t
            // 条件：nums[f] + nums[s] > nums[t]（因数组有序，t 越大越难满足）

            while (t < n && nums[f] + nums[s] > nums[t])
            {
                ++t; // t 移到第一个不满足条件的位置
            }
            // 有效三元组数量 = 满足条件的 t 的个数（从 s+1 到 t-1）
            if (t == s)
                break;
            sm += (t - 1) - s;
        }
    }
    return sm;
}
//--------------------------------------------------------------------------------------
//三数之和
//https://leetcode.cn/problems/3sum/
//本题难点是左右双指针与去重操作
//再做时可以考略set

vector<vector<int>> threeSum(vector<int> &nums)
{
    vector<vector<int>> vv;
    vector<int> v;
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int f = 0;
    for (; f < n - 2; f++)
    {
        if(f>0&&nums[f]==nums[f-1])
        continue;
        int r=nums[f];
        int s=f+1;
        int t = n-1;//>1  <0
        while(s<t)
        {
            int fg=nums[t]+nums[s]+r;
            if(fg>0)
            t--;
            else if(fg<0)
            s++;
            else
            {
                v={nums[f],nums[s],nums[t]};
                vv.push_back(v);
                s++;
                t--;
                while(s<t&&nums[s]==nums[s-1])
                s++;
                while(s<t&&nums[s]==nums[s-1])
                t--;

            }

        }


    }
    return vv;
}
//--------------------------------------------------------------------------------------

bool isUnique(string astr)
{
    int r = 0;
    bool ret = true;
    for (auto a : astr)
    {
        int n = 1 << (a - 'a');
        if ((r & n) != 0)
        {
            ret = false;
            break;
        }
        r |= n;
    }
    return ret;
}

//--------------------------------------------------------------------------------------
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        unordered_set<char> st;
        int lgg=0;
        int l=0;
        int r=0;
        for(;r<n;r++)
        {
            if(!st.count(s[r]))
            {
                st.insert(s[r]);

            }
            else
            {
                if(r-l>lgg)
                lgg=r-l;
                int tmp=s.find(s[r],l);
                for(;l<tmp;l++)
                st.erase(s[l]);
                l++;

            }


        }
        if(r-l>lgg)
        lgg=r-l;
        return lgg;

        
    }
//--------------------------------------------------------------------------------------
    // int minSubArrayLen(int target, vector<int>& nums) {
    //     int r=0;
    //     int l=0;
    //     int n=nums.size();
    //     int sm=0;
    //     int len=INT_MAX;
    //     while(r<n)
    //     {
    //             sm+=nums[r];

    //         while(sm>=target){
    //             if(r-l<len)
    //             len=r-l;
    //             l++;

    //         }
    //         r++;

    //     }
        
    // }
//--------------------------------------------------------------------------------------
int minOperations(vector<int>& nums, int x) {
        int l=0;
        int r=0;
        int sm=0;
        for(auto i:nums)
        sm+=i;
        if(sm<x) return -1;
        int lsm=0;
        int rsm=sm;
        int n=nums.size();
        int len=INT_MAX;
        while(l<n&&lsm<=x)
        {
            while (rsm + lsm > x&&r<n)
            {

                rsm -= nums[r];
                r++;
            }
            if (rsm+lsm==x)
            {
                int L=n-r+l;
                if(L<len)
                len=L;
            }
            lsm+=nums[l];
            l++;

        }
        if (rsm + lsm == x)
        {
            int L = n - r + l + 1;
            if (L < len)
                len = L;
        }
        return len==INT_MAX?-1:len;
    }


//-------------------------------------------------------------------------------------更具普适性解法
    int totalFruit(vector<int>& fruits) {
        
        int x1=0;
        int x2=fruits[0];
        int l=-1;
        int r=0;
        int d=0;//标记最新数字，下一个left
        int n=fruits.size();
        // if(n==1)
        // return 1;
        int len=1;
        for(;r<n;r++)
        {
            if(fruits[r]!=x1&&fruits[r]!=x2)
            {
                if(len<r-l)
                len=r-l;
                x1=x2;
                x2=fruits[r];
                l=d;
                d=r;


            }
            else
            {
                if (fruits[r] != fruits[d])
                {
                    d = r;
                    x1 = x2;
                    x2 = fruits[r];
                }
            }
        }
        if(len<r-l)
        len=r-l;
        return len;

        
    }
//--------------------------------------------------------------------------------------
// class Solution {
// public:
//     int totalFruit(vector<int>& fruits) {
        
//         int x1=fruits[0];
//         int x2=fruits[1];
//         int l=0;
//         int r=2;
//         int d=x1==x2?0:1;
//         int n=fruits.size();
//         if(n==1)
//         return 1;
//         int len=2;
//         for(;r<n;r++)
//         {
//             if(fruits[r]!=x1&&fruits[r]!=x2)
//             {
//                 if(len<r-l)
//                 len=r-l;
//                 x1=x2;
//                 x2=fruits[r];
//                 l=d;
//                 d=r;


//             }
//             else{
//                 if(fruits[r]!=fruits[d])
// {                d=r;
//                 x1=x2;
//                 x2=fruits[r];}

                

//             }

//         }
//         if(len<r-l)
//         len=r-l;
//         return len;

        
//     }
// };
//--------------------------------------------------------------------------------------
void PrefixSum()//本题目关键在于预处理前缀和数组
{
    int n,m;
    cin>>n>>m;
    vector<int> v(n+1);
    vector<long long> V(n+1);
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
        
        V[i]=V[i-1]+v[i];


    }
    int l ,r;
    while(m--)
    {
        cin>>l>>r;
        cout<<V[r]-V[l-1]<<endl;
    }
    // for(auto i:v)
    // {
    //     cout<<i;
    // }


}
//--------------------------------------------------------------------------------------
int pivotIndex(vector<int> &nums)
{
    int n = nums.size();
    vector<int> v(n);
    v[0] = nums[0];
    for (int i = 1; i < n; i++)
    {
        v[i] = v[i - 1] + nums[i];
    }
    if (v[n - 1] == 0)
        return 0;
    int ans = v[n - 1];
    for (int i = 1; i < n; i++)
    {
        if (ans == v[i] + v[i - 1])
            return i;
    }
    return -1;
}
//--------------------------------------------------------------------------------------
    int SearchInsert(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() - 1;
        int mid;
        int ans = nums.size();
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] > target)
                r = mid - 1;
            else {
                ans = mid;
                l = mid + 1;
            }
        }
        return ans;
    }
//--------------------------------------------------------------------------------------
    vector<int> productExceptSelf(vector<int>& nums) {
        int n=nums.size();
        vector<int> f(n);
        vector<int> g(n);
        f[0]=1;
        g[n-1]=1;
        for(int i=0;i<n;i++)
        {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--)
        {
            g[i]=g[i+1]*nums[i+1];
        }
        vector<int> r(n);
        for(int i=0;i<n;i++)
        r[i]=f[i]*g[i];
        return r;
                
    }
//--------------------------------------------------------------------------------------
//https://leetcode.cn/problems/subarray-sum-equals-k/
//和为 K 的子数组
    int subarraySum(vector<int> &nums, int k)
    {
        int sum=0;
        int ret=0;
        unordered_map<int,int> hash;
        hash[0]=1;
        for(auto i:nums)
        {
            sum+=i;
            ret+=hash[sum-k];
            hash[sum]++;

        }
        return ret;
    }
//--------------------------------------------------------------------------------------
    // int findMaxLength(vector<int>& nums) {
    //       int R=0;
    //       int r=0;
    //       int x=nums[0];
    //       int c=0;
    //       int o=0;
    //       int i=0;
    //       while(i<nums.size())
    //       {
    //         if (x==nums[i])
    //         {
    //             c++;
    //             i++;
    //             }
    //         else{
    //             r=c<o?c:o;
    //             o=c;
    //             c=0;
    //             R=R>r?R:r;
    //             x=nums[i];
    //         }
    //       }
    //       r = c < o ? c : o;
    //       R = R > r ? R : r;
    //       return 2*R;


        
    // }


//--------------------------------------------------------------------------------------
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> hash;
        int r=0;
        int R=0;
        hash[1]=-1;
        for(int i=1;i<nums.size();i++)
        {
            nums[i]=nums[i-1]+nums[i];
        }
        for(int i=0;i<nums.size();i++)
        {

            if(!hash.count(2*nums[i]-i))
            {
                hash[2* nums[i]-i]=i;
            }
            else{
                r=i-hash[2*nums[i]-i];
                if(r>R)R=r;
            }

        }
        return R;
        
    }
//--------------------------------------------------------------------------------------
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        int ct=0;
        hash[0]=1;

        for(int i=1;i<nums.size();i++)
        {
            nums[i]+=nums[i-1];
        }
        for(int i=0;i<nums.size();i++)
        {
            nums[i]%=k;
            if(nums[i]<0)
            nums[i]+=k;
            if(!hash.count(nums[i]))
            hash[nums[i]]++;
            else{
                ct+=hash[nums[i]];
                hash[nums[i]]++;

            }
        }
        return ct;
        
    }
//--------------------------------------------------------------------------------------
        void mergesort(vector<int>& nums,vector<int>& tmp,int l,int r)
    {
        if(l>=r)return;
        int mid=(l+r)/2;
        int b=l;
        int b1=l,e1=mid,b2=e1+1,e2=r;
        mergesort(nums,tmp,b1,e1);
        mergesort(nums,tmp,b2,e2);
        while(b1<=e1&&b2<=e2)
        {
            if(nums[b1]>nums[b2])
            tmp[l++]=nums[b2++];
            else
            tmp[l++]=nums[b1++];
        }
                while(b1<=e1)
        {

               tmp[l++]=nums[b1++];
        }
                while(b2<=e2)
        {
            tmp[l++]=nums[b2++];
        }
        for(int i=b;i<=r;i++)
        {
            nums[i]=tmp[i];
        }
        





    }
//--------------------------------------------------------------------------------------
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int>> dp(n+1, vector<int>(m+1));
        vector<vector<int>> arr(n, vector<int>(m));

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] =
                    dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i-1][j-1];
                    cout<<dp[i][j]<<" ";

            }
            cout<<endl;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int a=i+1+k>n?n:i+1+k;
                int b=j+1+k>m?m:j+1+k;
                int c=i-k>0?i-k:0;
                int d=j-k>0?j-k:0;
                arr[i][j] =
                    dp[a][b] - dp[a][d] - dp[c][b] + dp[c][d];
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
        return arr;


    }
//--------------------------------------------------------------------------------------
    void HT(vector<int> &A, vector<int> &B, vector<int> &C, int n)
    {
        if (n == 1)
        {
            int b = A.back();
            A.pop_back();
            C.push_back(b);
            return;
        }
        HT(A, C, B, n - 1);
        int b = A.back();
        A.pop_back();
        C.push_back(b);
        HT(B, A, C, n - 1);
        return;
    }

    void hanota(vector<int> &A, vector<int> &B, vector<int> &C)
    {
        HT(A, B, C, A.size());
    }
//--------------------------------------------------------------------------------------
    int randkey(vector<int>& nums, int l, int r) {
        int idx = l + rand() % (r - l + 1);
        return nums[idx];
    }   

int Find(vector<int>& nums, int k,int l,int r)
{
        if(l==r) return nums[l];
        int L=l-1,R=r+1;
        int key=randkey(nums,l,r);

        int i=l;
        while(i<R)
        {
            if(nums[i]<key)swap(nums[++L],nums[i++]);
            else if(nums[i]==key)i++;
            else swap(nums[--R],nums[i]);


        }
        if(r-R+1>=k)return Find(nums,k,R,r);
        if(r-L>=k) return key;
        return Find(nums,k-r+L,l,L);

}

int findKthLargest(vector<int>& nums, int k) {
    return Find(nums,k,0,nums.size()-1);

    }
//--------------------------------------------------------------------------------------
void Sort(vector<int>& nums, int k,int l,int r)
{
        if(l==r) return;
        int L=l-1,R=r+1;
        int key=randkey(nums,l,r);

        int i=l;
        while(i<R)
        {
            if(nums[i]<key)swap(nums[++L],nums[i++]);
            else if(nums[i]==key)i++;
            else swap(nums[--R],nums[i]);


        }
        int a=L-l+1;
        int b=R-L-1;
        if(k<a) {Sort(nums,k,l,L);return;}
        if(k<=a+b)return;
        Sort(nums,k-a-b,R,r);return;


}
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        Sort(stock,cnt,0,stock.size()-1);
        return {stock.begin(),stock.begin()+cnt};
    }

//--------------------------------------------------------------------------------------
    string removeDuplicates(string s) {
        stack<char> st;
        for(auto i:s)
        {
            if(!st.empty())
            {
                if(st.top()==i)
                st.pop();
                else st.push(i);

            }
            else
            st.push(i);


        }
        string r;
        while(!st.empty())
        {
            char i=st.top();
            st.pop();
            r=i+r;
        }
        return r;
    }
//--------------------------------------------------------------------------------------
    bool backspaceCompare(string s, string t) {
        string S;
        string T;
        for(auto i:s)
        {
            if(i=='#'&&!S.empty())S.pop_back();
            else S.push_back(i);
        }
        for(auto i:t)
        {
            if(i=='#'&&!T.empty())T.pop_back();
            else T.push_back(i);
        }
        return T==S;

        
    }
//--------------------------------------------------------------------------------------
    int calculate(string s) {
        vector<int> st;
        int sg=0;
        int sm=0;
        for(int i=0;i<s.size();i++)
        {
            if(s[i]=='+')
            sg=0;
            else if(s[i]=='-')
            sg=1;
            else if(s[i]=='*')
            sg=2;
            else if(s[i]=='/')
            sg=3;
            else if(s[i]==' ');
            else
            {
                while(isdigit(s[i]))
            {
                sm=sm*10+(s[i]-'0');
                i++;
                }
                switch(sg){
                    case 0:st.push_back(sm);break;
                    case 1:st.push_back(-sm);break;
                    case 2:st.back()*=sm;break;
                    case 3:st.back()/=sm;break;

                }
                i--;
                sm=0;

                
            }
        }
        int r=0;
        for(int i:st)
        {
            r+=i;
        }
        return r;
    }
//--------------------------------------------------------------------------------------
  struct ListNode {
      int val;
      ListNode *next;
      ListNode() : val(0), next(nullptr) {}
      ListNode(int x) : val(x), next(nullptr) {}
      ListNode(int x, ListNode *next) : val(x), next(next) {}
  };

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==nullptr)return head;
        if(k==1)return head;
        ListNode*t=head;
        int ct=1;
        while(ct<k&&t)
        {
            t=t->next;
            ct++;
        }
        if(t==nullptr)return head;
        ListNode*pre=nullptr;
        ListNode*cur=head;
        auto T=t->next;
        while(cur!=T)
        {
            ListNode*next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        head->next=reverseKGroup(cur,k);
        return t;


    }
//--------------------------------------------------------------------------------------
struct cmp{
    bool operator()(const ListNode*l1,const ListNode*l2)
    {
        return l1->val>l2->val;
    }
};    
ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> q;
        for(auto l:lists)
        {
            q.push(l);
        }
        ListNode*h=new ListNode();
        auto c=h ;
        while(!q.empty())
        {
            auto a=q.top();
            q.pop();
            c->next=a;
            c=a;
            if(a->next)
            q.push(a->next);
        }
        return h->next;
    }
//--------------------------------------------------------------------------------------
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int>hash;
        for(int i=0;i<nums.size();i++)
        {
            if(hash.count(target-nums[i]))
            {
                vector<int> v={hash[target-nums[i]],i};
                return v;

            }
            else
            hash[nums[i]]=i;

        }
    }
//--------------------------------------------------------------------------------------
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int>hash;
        for(auto i:nums)
        {
            if(hash.count(nums[i]))
            {
                return 1;
            }
            else
            hash.insert(nums[i]);
        }
        return 0;
    }
//--------------------------------------------------------------------------------------
    // bool containsDuplicate(vector<int>& nums) {
    //     unordered_set<int>hash;
    //     for(auto i:nums)
    //     {
    //         if(hash.count(nums[i]))
    //         {
    //             return 1;
    //         }
    //         else
    //         hash.insert(nums[i]);
    //     }
    //     return 0;
    // }
//--------------------------------------------------------------------------------------
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int>hash;
        for(int i=0;i<nums.size();i++)
        {
            if(hash.count(nums[i]))
            {
                if(i-hash[nums[i]]<=k)return 1;
                hash[nums[i]]=i;
            }
            else
            hash[nums[i]]=i;
        }
        return 0;
    }
//--------------------------------------------------------------------------------------
    bool CheckPermutation(string s1, string s2) {
        unordered_map<char,int> h1;
        unordered_map<char,int> h2;
        for(auto i:s1)
        {
            h1[i]++;
        }
        for(auto i:s2)
        {
            h2[i]++;
        }
        return h1==h2;
        
    }
//--------------------------------------------------------------------------------------
    int waysToStep(int n) {
     vector<int> dp(n+1);
     dp[1]=1;
     dp[2]=2;
     dp[3]=4;
     int mod=1e9+7;
     if(n<=3)return dp[n];
     for(int i=4;i<=n;i++)
     {
        dp[i]=(dp[i-1]+dp[i-2]%mod+dp[i-3])%mod;

     }
     return dp[n];

    }
//--------------------------------------------------------------------------------------
// int min(int a,int b)
// {
//     return a>b?b:a;
// }    
int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1);
        if(n==1)return 0;
        dp[0]=dp[1]=0;
        for(int i=2;i<=n;i++)
        {
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);

        }
        return dp[n];

    }
//--------------------------------------------------------------------------------------
    int numDecodings(string s) {
        int n=s.size();
        vector<int> dp(n);
        if(n==0)return 0;
        if(s[0]!='0')dp[0]=1;
        else dp[0]=0;
        if(n==1)return dp[0];
        if(s[1]!='0')
        {
            dp[1]=dp[0];
            if(s[0]=='1')
            dp[1]++;
            else if(s[0]=='2')
            {
                if(s[1]<'7')
                dp[1]++;
            }

            }
        else
        {
            if(s[0]=='1'||s[0]=='2')
            dp[1]=dp[0];

            }
        if(n==2)return dp[1];

        for(int i=2;i<n;i++)
        {
                   if(s[i]!='0')
        {
            dp[i]=dp[i-1];
            if(s[i-1]=='1')
            dp[i]=dp[i-1]+dp[i-2];
            else if(s[i-1]=='2')
            {
                if(s[i]<'7')
                dp[i]=dp[i-1]+dp[i-2];
            }

            }
        else
        {
            if(s[i-1]=='1'||s[i-1]=='2')
            if(s[i-2]=='1'||s[i-2]=='2')
            dp[i]=dp[i-1]-dp[i-2];
            else
            dp[i]=dp[i-1];

            }
        }
        return dp[n-1];
    }
//--------------------------------------------------------------------------------------
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
     map<map<char,int>,vector<string>> h;
     vector<vector<string>> vv;
     for(auto i :strs)
     {
        map<char,int> h1;
        for(auto j:i)
        {
            h1[j]++;
        }
        h[h1].push_back(i);
    }
    for (const auto& pair : h) {
        // pair.first 是键，pair.second 是值
        vv.push_back(pair.second);
    }
    return vv;



    }
//--------------------------------------------------------------------------------------
    int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }

    }
    return dp[m][n];
    } 
//--------------------------------------------------------------------------------------
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    int m=obstacleGrid.size();
    int n=obstacleGrid[0].size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(obstacleGrid[i-1][j-1]!=1)
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }

    }
    return dp[m][n];
    }
//--------------------------------------------------------------------------------------
    int jewelleryValue(vector<vector<int>>& frame) {
    int m=frame.size();
    int n=frame[0].size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));
        for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
        }

    }
    return dp[m][n];
    }
//--------------------------------------------------------------------------------------
int Min(int a,int b,int c)
{
    return min(min(a,b),c);
}    
int minFallingPathSum(vector<vector<int>>& matrix) {
    int m=matrix.size();
    int n=matrix[0].size();
    vector<vector<int>> dp(m+1,vector<int>(n+2,INT_MAX));
    for(int j=1;j<=n;j++)
    {
        dp[1][j]=matrix[0][j-1];
    }
    for(int i=2;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=Min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+matrix[i-1][j-1];


        }
    }
    int mn=INT_MAX;
    for(int j=1;j<=n;j++)
    {
        if(dp[m][j]<mn)
        mn=dp[m][j];
    }
    return mn;
    }
//--------------------------------------------------------------------------------------
    int minPathSum(vector<vector<int>> &grid)
    {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
        dp[0][1]=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];

    }
//--------------------------------------------------------------------------------------
    int massage(vector<int> &nums)
    {
        int n=nums.size();
        if(n==0)return 0;
        vector<int> f(n),g(n);
        f[0]=nums[0];
        g[0]=0;
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);

        }
        return max(f[n-1],g[n-1]);

    }
//--------------------------------------------------------------------------------------
    int rob1(vector<int>& nums) {
        int n=nums.size();
        if(n==0)return 0;
        vector<int> f(n),g(n);
        f[0]=nums[0];
        g[0]=0;
        for(int i=1;i<n;i++)
        {
            f[i]=g[i-1]+nums[i];
            g[i]=max(f[i-1],g[i-1]);

        }
        return max(f[n-1],g[n-1]);
    }
//--------------------------------------------------------------------------------------
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };    
// vector<string> ret;
    // vector<string> binaryTreePaths(TreeNode *root)
    // {
    //     string path;
    //     BT(root->left,path);
    // }
    // void BT(TreeNode *root, string path)
    // {
    //     path+=to_string(root->val);
    //     if (root->left == nullptr && root->right==nullptr)
    //     {
    //         ret.push_back(path);
    //         return;
    //     }
    //     path+="->";
    //     if(root->left) BT(root->left,path);
    //     if(root->right)BT(root->right,path);


    // }
//--------------------------------------------------------------------------------------
    // int ret=0;
    // int sumNumbers(TreeNode* root) {
    //     if(!root)return ret;
    //     SN(root,0);
    //     return ret;
    // }
    // void SN(TreeNode*root,int presum)
    // {
    //     presum=10*presum+root->val;
    //     if (root->left == nullptr && root->right==nullptr)
    //     {
    //         ret+=presum;
    //         return;
    //     }

    //     if(root->left) SN(root->left,presum);
    //     if(root->right)SN(root->right,presum);

    // }
//--------------------------------------------------------------------------------------
    TreeNode* pruneTree(TreeNode* root) {
        if(!root) return nullptr;
        TreeNode*l=pruneTree(root->left);
        if(!l) root->left=nullptr;
        TreeNode*r=pruneTree(root->right);
        if(!r) root->right=nullptr;
        if(l==nullptr&&r==nullptr&&root->val==0)
        {
            root=nullptr;
        }
        return root;
    }
//--------------------------------------------------------------------------------------
long long pre=LONG_LONG_MIN;    
bool isValidBST(TreeNode* root) {
        if(root->left==nullptr&&root->right==nullptr)
        {
            if(root->val>pre)
            {
                pre=root->val;
                return 1;
            }
            return 0;
        }
        if(root->left)
        {
            if(!isValidBST(root->left))
            return 0;
            
        }
        if(root->val>pre)
        {
            pre=root->val;
        }
        else return 0;
        if(root->right)
        {
            if(!isValidBST(root->right))
            return 0;
            
        }
        return 1;


        
    }
//--------------------------------------------------------------------------------------
int cnt=0;
// int ret=0;    
// int kthSmallest(TreeNode* root, int k) {
//         if(root->left==nullptr&&root->right==nullptr)
//         {
//             cnt++;
//             if(cnt==k)
//             {
//             ret=root->val;

//             }
//             return ret;
//         }
//         if(root->left)
//         {
//             kthSmallest(root->left, k);
//             if(cnt==k)
//             return ret;
//             }
//         cnt++;
//         if (cnt == k)
//         {
//             ret = root->val;
//             return ret;
//         }
//         if(root->right)
//         {
//             kthSmallest(root->right, k);
//             if(cnt==k)
//             return ret;
//             }
//         return ret;
//         }



//--------------------------------------------------------------------------------------
    int lastStoneWeight(vector<int>& stones) {
       priority_queue<int> q;
       for(auto i:stones)
       {
        q.push(i);
       } 
       while(q.size()>1)
       {
        auto a=q.top();
        q.pop();
        auto b=q.top();
        q.pop();
        a-=b;
        if(a)
        q.push(a);
       }
       if(q.size())
       return q.top();
       return 0;


       
    }
//--------------------------------------------------------------------------------------
typedef pair<string,int> PSI;
// struct cmp
// {
//     bool operator()(const PSI &p1,const PSI &p2)
//     {
//         if(p1.second==p2.second)
//         {
//             return p1.first>p1.first; 
//         }
//         return p1.second<p2.second;

//     }
//     /* data */
// };

// vector<string> topKFrequent(vector<string>& words, int k) {
//         priority_queue<PSI ,vector<PSI>,cmp> q;
//         unordered_map<string,int> hash;
//         vector<string> s(k);
//         for(auto i:words)
//         {
//             hash[i]++;
//         }
//         for(auto i:hash)
//         {
//             q.push(i);
//             if(q.size()>k)
//             q.pop();

//         }
//         for(int i=0;i<k;i++)
//         {
//             s[i]=q.top().first;
//             q.pop();
//         }
//         return s;


// }
//--------------------------------------------------------------------------------------
struct MedianFinder{
    
    vector<int> v;
    priority_queue<int> q1;
    priority_queue<int,vector<int>,greater<int>> q2;

    void addNum(int num) {
        v.push_back(num);
        if(num<q1.top())
        {
            q1.push(num);
        }
        else
        q2.push(num);
        while(q1.size()<(v.size()/2+1)&&(!q2.empty()))
        {
            q1.push(q2.top());
            q2.pop();
        }
        while(q1.size()>(v.size()/2+1))
        {
            q2.push(q1.top());
            q1.pop();
        }
    }
    
    double findMedian() {
        if(v.size()%2==0)
        {
            int a=q1.top();
            q1.pop();
            int b=q1.top();
            q1.push(a);
            return (a+b)/2.0;


        }
        return q1.top();
    }
};
//--------------------------------------------------------------------------------------
int strStr(string haystack, string needle)
{
    int N=haystack.size();
    int n=needle.size();
    vector<int>pi(n);
    for (int i = 1; i < n; i++)
    {
        int len=pi[i-1];
        while(len!=0&&needle[i]!=needle[len])
        {
            len=pi[len-1];
        }
        if (needle[i] == needle[len])
        {
            pi[i] = len + 1;
        }
    }
    for (int i = 0,len=0; i < N; i++)
    {
        while(len&&haystack[i]!=needle[len])
        {
            len=pi[len-1];
        }
        if (haystack[i] == needle[len])
        {
            if(++len==n)
            return i-n+1;
        }

    }

        return -1;
}
//--------------------------------------------------------------------------------------

// int strStr(string haystack, string needle)
// {
//     haystack=needle+'#'+haystack;
//     int N=haystack.size();
//     int n=needle.size();
//     vector<int>pi(N);
//     for (int i = 1; i < N; i++)
//     {
//         int len=pi[i-1];
//         while(len&&haystack[i]!=haystack[len])
//         {
//             len=pi[len-1];
//         }
//         if (haystack[i] == haystack[len])
//         {
//             pi[i] = len + 1;
//             if(pi[i]==n)
//             return i-2*n;
//         }
//     }


//         return -1;
// }
//--------------------------------------------------------------------------------------
    int deleteAndEarn(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int v[10001]={0};
        int n=nums.size();
        for(auto a:nums)
        {
            v[a]+=a;
        }
        vector<int>f(10001);
        vector<int>g(10001);
        for(int i=1;i<=10000;i++)
        {
            f[i]=g[i-1]+v[i];
            g[i]=max(g[i-1],f[i-1]);
        }
        return max(f[10000],g[10000]);

    }
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------
//--------------------------------------------------------------------------------------


int main()
{
    MedianFinder m;
    m.addNum(-1);
        cout<<m.findMedian();
    m.addNum(-2);
        cout<<m.findMedian();
    m.addNum(-3);
        cout<<m.findMedian();
    m.addNum(-4);
        cout<<m.findMedian();
    m.addNum(-5);
    cout<<m.findMedian();
    // vector<vector<int>>vv={{2,1,3},{6,5,4},{7,8,9}};
    // cout<<minFallingPathSum(vv);

    return 0;
}

// int main()
// {
//     string s="2611055971756562";
//     cout<<numDecodings(s);
//     // vector<int> nums={1,2,3,4,5};
//     // ListNode*h= new ListNode();
//     // ListNode*pre=h;
//     // for(auto i:nums)
//     // {
//     //     ListNode*c= new ListNode(i);
//     //     pre->next=c;
//     //     pre=c;
//     // }
//     // reverseKGroup(h->next,2);
//     // cout<<calculate("3+2*2");
//     // vector<int>tmp(nums.size());
//     // // vector<vector<int>> vv={{1,2,3},{4,5,6},{7,8,9}};
//     // Print(inventoryManagement(nums, 8));
//     // vector<int> A={1,0};
//     // vector<int> B;
//     // vector<int> C;

//     // mergesort(nums,tmp,0,nums.size()-1);
//     // matrixBlockSum(vv,1);
//     // hanota(A, B, C);
//     // Print(nums);
//     // threeSum(h);
//     // cout<<3/2;
//     // PrefixSum();
//     // productExceptSelf(h);
//     // cout<<totalFruit(h);

//     return 0;
// }
